
import org.junit.jupiter.api.Test;

import java.util.*;

public class Offer {

    // 剑指 Offer 06. 从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> ints = new ArrayList<>();
        while (head != null) {
            ints.add(head.val);
            head = head.next;
        }
        int[] result = new int[ints.size()];
        for (int i = 0; i < ints.size(); i++) {
            result[i] = ints.get(ints.size() - 1 - i);
        }
        return result;
    }

    //剑指 Offer 07. 重建二叉树
    // 前序中左右【根, [左] , [右] ] 中序左中右[ [左] , 根 , [右] ]
    // 自研写法，有一个bug处理不了
    /*public static TreeNode buildTree(int[] preorder, int[] inorder) {
        // 中序的左子树为空，则到头了
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        // 前序的第一个节点是根节点
        int root = preorder[0];
        int root_index_right = 0;
        // 找到中序的的左子树
        for (int i = 0; i < inorder.length; i++) {
            if (root == inorder[i]) {
                root_index_right = i;
                break;
            }
        }
        TreeNode treeNode = new TreeNode(root);
        // 前序中左右【根, [左] , [右] ] 中序左中右[ [左] , 根 , [右] ]
        // 前序中左右【[左] , [右] ] 中序左中右[ [左]]
        treeNode.left = buildTree(Arrays.copyOfRange(preorder, 1, preorder.length),
                Arrays.copyOfRange(inorder, 0, root_index_right));

        // 前序中左右【根, [左] , [右] ] 中序左中右[ [左] , 根 , [右] ]
        // 前序中左右【[左] , [右] ] 中序左中右[ [右]]
        //root_index_right 是因为root_index_right是根节点，
        // 剔除前序的根和左子一直在拷贝，把自己路走死了，去除不掉采用官方的写法吧
        int root_index_left = 0;
        for (int i = 0; i < preorder.length; i++) {
            if (treeNode.left == null) break;
            else if (treeNode.left.val == preorder[i]) {
                root_index_left = i;
                break;
            }
        }
        treeNode.right = buildTree(Arrays.copyOfRange(preorder, root_index_left + 1, preorder.length),
                Arrays.copyOfRange(inorder, root_index_right + 1, inorder.length));
        return treeNode;
    }*/
    // 官方写法
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }

        return myBuildTree(preorder, inorder,
                0, preorder.length - 1,
                0, inorder.length - 1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder,
                                int preorder_start, int preorder_end,
                                int inorder_start, int inorder_end) {
        if (preorder_start > preorder_end) return null;
        //
        int rootVal = preorder[preorder_start];
        TreeNode root = new TreeNode(rootVal);

        // 找到中序的的左子树
        int inorder_root_index = indexMap.get(rootVal);

        // 根索引-开始索引 = 右子树大小
        int right_size = inorder_root_index - inorder_start;
        // 前序中左右【根, [左] , [右] ] 中序左中右[ [左] , 根 , [右] ]
        // 前序中左右【 [左 = 根+1 - 根+右子树大小] ] 中序左中右[ [左 = 开始节点 - 根-1 < -1表述不包括根>]]
        root.left = myBuildTree(preorder, inorder,
                preorder_start + 1, right_size + preorder_start,
                inorder_start, inorder_root_index - 1);

        // 前序中左右【根, [左] , [右] ] 中序左中右[ [左] , 根 , [右] ]
        // 前序中左右【 [右 = 左子树+1+开始的位置 - 末尾] ] 中序左中右[ [ 右 = 根+1 - 末尾]
        root.right = myBuildTree(preorder, inorder,
                right_size + preorder_start + 1, preorder_end,
                inorder_root_index + 1, inorder_end);

        return root;
    }

    public int cuttingRope(int n) {
        int[] ints = new int[n + 1];
        // 外层找第几个数
        for (int i = 2; i <= n; i++) {
            int tempMax = 0;
            // 内层计算数的最大值 所以肯定不能超过i
            for (int j = 1; j < i; j++) {
                // 拆分成两个 j*（i-j）i-j 不可拆分 和 j*ints[i - j] 可拆分
                int max = Math.max(j * (i - j), j * ints[i - j]);
                // 和之前计算的最大进行比较
                tempMax = Math.max(max, tempMax);
            }
            ints[i] = tempMax;
        }
        return ints[n];
    }

    public static int cuttingRope1(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }

    // ------------------------------------------------------------------
    // 剑指 Offer 09. 用两个栈实现队列
    class CQueue {
        ArrayDeque<Integer> inStack = new ArrayDeque<>();
        ArrayDeque<Integer> outStack = new ArrayDeque<>();

        public CQueue() {

        }

        public void appendTail(int value) {
            inStack.push(value);
        }

        public int deleteHead() {
            if (outStack.isEmpty()) {
                if (inStack.isEmpty())
                    return -1;
                // 倒装进出栈的
                while (!inStack.isEmpty()) {
                    outStack.push(inStack.pop());
                }
            }
            return outStack.pop();
        }
    }

    // ------------------------------------------------------------------
    //剑指 Offer 11. 旋转数组的最小数字
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];

    }

    // 剑指 Offer 16. 数值的整数次方
    public double myPow(double x, int n) {
        return n > 0 ? myPow1(x, n) : 1.0 / myPow1(x, -n);
    }

    private double myPow1(double x, int n) {
        if (n == 0) return 1.0;
        double v = myPow1(x, n / 2);
        return n % 2 == 0 ? v * v : v * v * x;
    }
    // 剑指 Offer 17. 数值的整数次方
    public int[] printNumbers(int n) {
        int result = 0; 
        int[] resultNums = new int[(int)Math.pow(10,n)-1];
        for(int i=0 ; i<resultNums.length;i++){
            resultNums[i] = i+1;
        }
        return resultNums;
    }

    public int lastRemaining(int n, int m) {
        return f(n, m);
    }

    public int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = f(n - 1, m);
        return (m + x) % n;
    }

    public static void main(String[] args) {
        Node node = new Node(4);
        node.right = new Node(5);
        node.left = new Node(2, new Node(1), new Node(3));
        Offer offer = new Offer();
        Node node1 = offer.treeToDoublyList(node);
    }

    // 剑指 Offer 36. 二叉搜索树与双向链表
    Node pre, head;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        // 因为默认pre 和 head 是null 所以参数带不进去
        this.treeToDoublyListDFS(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    void treeToDoublyListDFS(Node root) {
        if (root == null) return;
        treeToDoublyListDFS(root.left);
        if (pre != null) pre.right = root;
        else head = root;
        root.left = pre;
        pre = root;
        treeToDoublyListDFS(root.right);
    }

    //剑指 Offer II 119. 最长连续序列
    public int longestConsecutive(int[] nums) {
        // 数组为空直接返回
        if (nums.length == 0) return 0;
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int result = 1;
        for (Integer integer : set) {
            // 如果只判断是否包含+1的是否包含，运行会超时
            // 所以找到数组当中起始值开始统计长度
            if (!set.contains(integer - 1)) {
                int tempLength = 1;
                while (set.contains(++integer)) {
                    tempLength++;
                }
                if (result < tempLength)
                    result = tempLength;
            }
        }
        return result;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}
